//----------------------------------------------------------------------原根
#define maxp 1093033
int P[maxp+1],//素数表
    md[maxp+1];//最小素因子

/* 找出n所有素因子,存于D[]中*/
void fact(LL n,LL D[])
{
    int i;D[0]=0;
    for(i=1;n>1&&P[i]*P[i]<=n;i++)
    {
        if(n<maxp)break;
        if(n%P[i]==0){
            D[++D[0]]=P[i];
            while(n%P[i]==0)n/=P[i];
        }
    }
    while(n<maxp&&n>1){
        D[++D[0]]=md[n];
        while(md[n]==D[D[0]])n/=md[n];
    }
    if(n>1)//so now n is a prime,larger than maxp
        D[++D[0]]=n;
}

/* 遍历p-1的所有因子 */
int dfs(int k,LL p,LL D[],LL cur,int ly)
{
    if(ly>D[0]){
        if(cur==p-1)return 1;
        if(mod_pow(k,cur,p)==1)return 0;
        return 1;
    }
    LL tmp=(p-1)/cur;
    while(1)
    {
        if(dfs(k,p,D,cur,ly+1)==0)return 0;
        if(tmp%D[ly])break;
        tmp/=D[ly];
        cur*=D[ly];
    }
    return 1;
}

/* 主程序,返回:p的原根 */
int proot(LL p)
{
    LL i,D[100];
    fact(p-1,D);
    for(i=2;;i++)
    {
        if(dfs(i,p,D,1,1))return i;
    }
}

/* 好吧,楼上弱爆了,其实只要检查一下phi(n)/pi就行了*/
int generator (int p) {
	vector<int> fact;
	int phi = p-1,  n = phi;
	for (int i=2; i*i<=n; ++i)
		if (n % i == 0) {
			fact.push_back (i);
			while (n % i == 0)
				n /= i;
		}
	if (n > 1)
		fact.push_back (n);
 
	for (int res=2; res<=p; ++res) {
		bool ok = true;
		for (size_t i=0; i<fact.size() && ok; ++i)
			ok &= powmod (res, phi / fact[i], p) != 1;
		if (ok)  return res;
	}
	return -1;
}
